package com.arron.algorithm.leetcodetop100.二叉树;

import com.arron.algorithm.tree.TreeNode;

/**
 * 124. 二叉树中的最大路径和
 */
public class MaxPathSum {


    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
       if (root == null){
            return 0;
       }

       getPathSum(root);

        return max;
    }


    public int getPathSum(TreeNode root){
        if (root == null){
            return 0;
        }

        // 一个节点也可以，所以当节点值为负数时可以舍去
        int leftVal = Math.max(0,getPathSum(root.left));
        int rightVal = Math.max(0,getPathSum(root.right));

        max = Math.max(max,leftVal+rightVal+root.val);

        //选择一个比较大的路径和加上自己值
        return root.val+Math.max(leftVal,rightVal);
    }

}
